题目分析

这个题目是有个学弟问我的一个大厂的面试题，这个题目想法很奇妙，能想到这个解法就能够做出来，提示一下，我们要逆向思考，结果数组应该是什么样子？

模拟

有的同学会想到暴力搜索，反正每个状态只有两个后续状态，时间复杂度是$O(2^n)$，数据量不大时可以通过本方法求解。但是这个题目的解可以到达30，因此要运算$2^30=1e9$的次数，肯定会TLE，因此不能暴力去解。

我们想最后的结果是不是[A, M]这个形式，[A, M]也一定是[A, M-A]转移过来的呢？因此如果反向去推，是不是可以直接可以求出结果呢？

直接枚举[A, M-A]的值，因为不考虑顺序，可以令$A \le M-A $，因此只需要从1开始，遍历到M / 2即可。时间复杂度是$O(n)$

对于A和M-A，不需要一步一步的地推，如果M-A远大于A，可以直接省略多次减法操作，因为[A, M-A]也是[A, M-2A]得到的，[A, M-2A]是[A, M-3A]得到的，因此可以省略M / A次减法，直接变为[A, M-(M / A) x A]。

这里使用递归获取从[1, 1]到[A, B]的最小值，递归要有递归终止条件，当A = 1时，则直接返回B-1，因为从[1, 1]到[1, B]的方法，只有从[1, 1] -> [1, 2] -> [1, 3]-> … -> [1, B]操作B-1次。当A = 0时，其实不存在这种情况，直接返回最大值，因为M < 1e6，因此直接返回1000000即可。

因为x % y < 0.5x (y < x)，简单即可证明，当y > 0.5x时，x % y = x - y < 0.5x。当y <= 0.5x时，余数小于除数，因此x % y < y <=0.5x。所以x每次都以一半的速度递减，因此时间复杂度是O(log(n))。

综上所述，算法的**时间复杂度为$O(nlog(n))$，空间复杂度为$O(1)$**。

public int miniOperationTimes(int num) {
    int mini = num - 1;
    for (int y = 1; y <= num / 2; y++) {
        mini = Math.min(mini, getMini(num - y, y) + 1);
    }
    return mini;
}

private int getMini(int x, int y) {
    if (y == 0) {
        return 1000000;
    }
    if (y == 1) {
        return x - 1;
    }
    return x / y + getMini(y, x % y);
}

刷题总结

通过本题，我们学到的不仅仅是如何求解该问题，而是当我们做题遇到瓶颈时，不妨换个思路，逆向思考，可能问题就迎刃而解了。